package november.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author huangxin
 * @date 2019/11/19-19:48
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 5, 6, 6, 7, 10, 100};
        int index = binarySearch(arr, 0, arr.length - 1, 10);
        if (index == -1) {
            System.out.println("没有找到");
        } else {
            System.out.println("下标为" + index);
            System.out.println(arr[index]);
        }

//        System.out.println(binarySearch2(arr, 0, arr.length - 1, 6));
    }


    public static int binarySearch(int[] arr, int start, int end, int value) {
        if (start > end) {
            return -1;
        }
        System.out.println(1);
        int mid = (start + end) / 2;
        if (value > arr[mid]) {
            return binarySearch(arr, mid + 1, end, value);
        } else if (value < arr[mid]) {
            return binarySearch(arr, start, mid - 1, value);
        } else {
            return mid;
        }
    }

    /**
     * 获取所有查找的元素下标
     *
     * @param arr
     * @param start
     * @param end
     * @param value
     * @return
     */
    public static List<Integer> binarySearch2(int[] arr, int start, int end, int value) {
        if (start > end) {
            return null;
        }

        int mid = (start + end) / 2;
        if (value > arr[mid]) {
            return binarySearch2(arr, mid + 1, end, value);
        } else if (value < arr[mid]) {
            return binarySearch2(arr, start, mid - 1, value);
        } else {
            List<Integer> list = new ArrayList<>();

            //往左边查找
            int index = mid - 1;
            while (index >= 0 && arr[index] == value) {
                list.add(index);
                index--;
            }

            list.add(mid);
            //往右边查找
            index = mid + 1;
            while (index < arr.length && arr[index] == value) {
                list.add(index);
                index++;
            }
            return list;
        }
    }
}
